#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include  <unordered_map>


using namespace std;

class Solution1 {
public:
    using pii = pair<int, int>;
    int dx[3] = { -1,0,1 };
    bool check[1000][1000];

    int maxMoves(vector<vector<int>>& grid) {
        int m = grid.size(); int n = grid[0].size();

        function<int()> bfs = [&]() {
            queue<pii> q;
            for (int i = 0; i < m; ++i) q.push({ i, 0 });
            int res = 0;
            while (!q.empty())
            {
                int size = q.size();
                while (size--)
                {
                    auto a = q.front().first;
                    auto b = q.front().second;
                    q.pop();
                    for (int i = 0; i < 3; ++i)
                    {
                        int x = a + dx[i]; int y = b + 1;
                        if (x >= 0 && x < m && y < n && !check[x][y] && grid[x][y] > grid[a][b])
                        {
                            q.push({ x,y });
                            check[x][y] = true;
                        }
                    }
                }
                if (q.size()) res++;
            }
            return res;
        };

        return bfs();
    }
};

class Solution2 {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end(),
            [](vector<int>& v1, vector<int>& v2) {
                return v1[0] < v2[0];
            });
        int n = pairs.size();
        vector<int> dp(n, 1);
        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                if (pairs[i][0] > pairs[j][1]) dp[i] = max(dp[i], dp[j] + 1);
            }
        }

        return *max_element(dp.begin(), dp.end());
    }
};

class Solution3 {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        int n = arr.size();
        unordered_map<int, int> dp;
        int ans = 0;
        for (int i = 0; i < n; ++i)
        {
            dp[arr[i]] = dp[arr[i] - difference] + 1;
            ans = max(ans, dp[arr[i]]);
        }
        return ans;
    }
};

class Solution4 {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n = arr.size();
        unordered_map<int, int> mp;
        for (int i = 0; i < n; ++i) mp[arr[i]] = i;
        vector<vector<int>> dp(n, vector<int>(n, 2));
        int res = 2;
        for (int i = 1; i < n; ++i)
        {
            for (int j = i + 1; j < n; ++j)
            {
                int sub = arr[j] - arr[i];
                if (mp.count(sub) && mp[sub] < i)
                {
                    dp[i][j] = dp[mp[sub]][i] + 1;
                    res = max(res, dp[i][j]);
                }
            }
        }
        return res >= 3 ? res : 0;
    }
};

int main()
{
	return 0;
}